Standard Steady State Genetic Algorithms Can Hillclimb Faster than Mutation-only Evolutionary Algorithms

摘要

Explaining to what extent the real power of genetic algorithms lies in theability of crossover to recombine individuals into higher quality solutions isan important problem in evolutionary computation. In this paper we show how theinterplay between mutation and crossover can make genetic algorithms hillclimbfaster than their mutation-only counterparts. We devise a Markov Chainframework that allows to rigorously prove an upper bound on the runtime ofstandard steady state genetic algorithms to hillclimb the OneMax function. Thebound establishes that the steady-state genetic algorithms are 25% faster thanall standard bit mutation-only evolutionary algorithms with static mutationrate up to lower order terms for moderate population sizes. The analysis alsosuggests that larger populations may be faster than populations of size 2. Wepresent a lower bound for a greedy (2+1) GA that matches the upper bound forpopulations larger than 2, rigorously proving that 2 individuals cannotoutperform larger population sizes under greedy selection and greedy crossoverup to lower order terms. In complementary experiments the best population sizeis greater than 2 and the greedy genetic algorithms are faster than standardones, further suggesting that the derived lower bound also holds for thestandard steady state (2+1) GA.